'''
Created on May 22, 2009

@author: Roni
'''
import unittest
import graph
from cliques.cliqueStarSearch import cliqueStarSearch
from cliques.cliqueFinder import cliqueFinder

class test_potenial_clique(unittest.TestCase):


    def setUp(self):
        pass


    def tearDown(self):
        pass

    def testPotentialClique(self):
        pass
    
    def testPotentialBasedCliqueSearch(self):
        a_graph = graph.graph()
        nodes = ['n0','n1','n2','n3','n4']
        a_graph.add_nodes(nodes)
        a_graph.add_edge(nodes[0],nodes[1])
        a_graph.add_edge(nodes[0],nodes[2])
        a_graph.add_edge(nodes[1],nodes[2])
        a_graph.add_edge(nodes[2],nodes[3])
        a_graph.add_edge(nodes[3],nodes[4])
        k=3
        self.algorithm = cliqueStarSearch()
        self.algorithm.setup(a_graph, k,nodes[0])
        self.clique_finder = cliqueFinder()
        self.clique_finder.setup(a_graph)
        clique = self.clique_finder.find_clique(k, nodes)
        
        while self.algorithm.halt()==False:
            # DEBUG print "    Iteration [%d]" % self.algorithm.iteration
            # If clique exists in the graph, 
            # verify that hasn't been discovered yet
            if clique is not None:
                assert len(set(self.algorithm.expanded).intersection(clique))<k-1          
            self.algorithm.step()
            #self.algorithm.status()
        # If no clique exists - verify all nodes were expanded
        if clique is None:
            components = test_graph.connected_components()
            start_component = components[start_node]
            connected_nodes=filter(lambda x:components[x]==start_component,components.keys())
            assert self.algorithm.iteration==len(connected_nodes)
        else:
            self.clique_finder.setup(self.algorithm.ckg)                    
            clique = self.clique_finder.find_clique(k,self.algorithm.ckg.nodes())
            assert clique is not None
            assert len(clique)==k             
        






if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()